function clone_arr(arr){
  let new_arr = [];
  new_arr = arr.map(function (item) {
    return item;
  });
  return new_arr;
}
/**
 * 插入排序
 * @param arr
 */
let insertion_sort = function (arr) {
  function _insertion_sort(arr) {
    for (let i = 1; i < arr.length; i ++) {
      for (let j = i; j >= 0 && arr[j] < arr[j - 1]; j --) {
        exec(arr, j ,j - 1);
      }
    }
  }
  _insertion_sort(arr);
};

/**
 * 归并排序
 * @param arr
 */
let merge_sort = function (arr) {

  function merge(arr, lo, hi, mid) {
    //对左右两边有序的数组按大小进行归并
    let tmp_arr = [];
    for (let i = lo; i <= hi; i ++) {
      tmp_arr[i] = arr[i];
    }
    let i = lo;
    let l = lo;
    let r = mid + 1;
    //从左边开始取
    while (i <= hi) {
      if (l > mid) {
        arr[i] = tmp_arr[r ++];
      }
      else if (r > hi) {
        arr[i] = tmp_arr[l ++];
      }
      else if (tmp_arr[r] < tmp_arr[l]) {
        arr[i] = tmp_arr[r ++];
      }
      else{
        arr[i] = tmp_arr[l ++];
      }
      i ++;
    }
    return arr;
  }

  function sort(arr, lo, hi) {
    if (hi <= lo) return ;
    let mid = lo + (hi - lo) / 2;
    mid = parseInt(mid);
    // 排左半部分
    sort(arr, lo, mid);
    // 排右半部分
    sort(arr, mid + 1, hi);
    merge(arr, lo, hi, mid);
  }
  sort(arr, 0, arr.length - 1);
  return arr;
};

let quick_sort = function (arr) {
  function partition(arr, lo, hi) {
    let i = lo;
    let j = hi + 1;
    let v = arr[lo];
    while (true) {
      // 把选定的v 比v小的都放左边，比v大的都放右边
      while (arr[++ i] < v) {
        if (i == hi)
          break;
      }
      while (arr[-- j] > v) {
        if (j == lo)
          break;
      }
      //如果左右两边指针相遇，找j的位置结束
      if (i >= j)
        break;
      exec(arr, i, j);
    }
    //把v放到正确位置，返回j（v）的位置
    exec(arr, lo, j);
    return j;
  }

  function sort(arr, lo, hi) {
    if (lo >= hi) return;
    let j = partition(arr, lo, hi);
    sort(arr, lo, j - 1);
    sort(arr, j + 1, hi);
  }
  sort(arr, 0, arr.length - 1);
  return arr;
};

let shell_sort = function (arr) {
  function shell(arr) {
    let n = arr.length;
    let h = 1;
    while (h < n / 3) {
      h = 3*h + 1;
    }

    while (h >= 1) {
      for (let i = h; i < n; i ++) {
        for (let j = i; j >= h; j -= h) {
          if (arr[j] < arr[j - h]) {
            exec(arr, j, j - h);
          }
        }
      }
      h=(h-1)/3;
    }
  }
  shell(arr);
  return arr;
};

/**
 * 工厂方法
 * @param arr
 * @param sort_function
 * @param name
 * @returns {*}
 */
function doSort(arr, sort_function, name) {
  console.log(name);
  let rs_arr = clone_arr(arr);
  var start = new Date().getTime();
  sort_function(rs_arr);
  var end = new Date().getTime();
  console.log(end-start);
  return rs_arr;
}

let test_arr = gen_rand(100000);

let insertion_rs = doSort(test_arr, insertion_sort, '插入');
let merge_rs = doSort(test_arr, merge_sort, '归并');
let quick_rs = doSort(test_arr, quick_sort, '快排');
let shell_rs = doSort(test_arr, shell_sort, '希尔');

console.log(test_arr);
console.log(insertion_rs);
console.log(merge_rs);
console.log(quick_rs);
console.log(shell_rs);
console.log(test_arr);
